package dp.一维数组;


/**
 * https://leetcode.cn/problems/fibonacci-number/
 */
public class _509_斐波那契数 {

    int[] meno;

    public int fib(int n) {
        meno = new int[n + 1];
        return dp(n);
    }

    private int dp(int n) {
        if (n == 0 || n == 1) {
            meno[n] = n;
            return meno[n];
        }

        if (meno[n] != 0) {
            return meno[n];
        }

        meno[n] = dp(n - 1) + dp(n - 2);
        return meno[n];
    }
}
